A user sends and receives mails through a web browser in an online email service such as Gmail, available from Google Inc., Menlo Park, Calif., USA. Now assume that a mail is signed and then encrypted in such an environment, such as is performed through PGP or S/MIME. In other words, assume that a so-called Sign-then-Encrypt (StE) process is performed on the mail. A browser usually does not function to manage a signature generation key and an encryption key, and thus an StE process cannot be executed locally on a computer of the user. For this reason, a server holds information on a signature generation key and an encryption key, and also executes an StE process. For example, consider a case where a sender sends a recipient a mail after subjecting the mail to an StE process. In this case, a secret signature generation key of the sender and a public encryption key of the recipient are held on a server. The server uses these keys to execute the StE process on, and then send, a mail that the sender has created on a browser.
The secret signature generation key of the sender may be stolen if a malicious attacker (either an insider or an outsider) invades the server in the above environment. To cope with this, some sort of protection means is required. Japanese Unexamined Patent Application Publication No. Hei 7-87081 (Patent Literature 1) describes a method for preventing fraud in a key publicity center by not allowing the key publicity center to hold any secret signature generation key. However, Patent Literature 1 cannot provide a method for executing an StE process since the key publicity center does not hold a signature generation key from the beginning. C. Collberg, C. Thomborson and D. Low, “A Taxonomy of Obfuscating Transformations.” Technical Report 148, Department of Computer Science, University of Auckland. 1997 describes various techniques for obfuscating a program written in JAVA programming language or C. A lot of such obfuscation tools, including ones commercially available, exist and can be used to obfuscate a program for an StE process. However, these tools aim to make a program difficult to read, and are not capable of preventing the revealing of a secret key completely. S. Hohenberger, G. N. Rothblum, A. Shelat, and V. Vaikuntanathan, “Securely Obfuscating Re-Encryption,” Proceedings of TCC '07, 2007 (Non-patent Literature 2) describes a technique for obfuscating Re-Encryption (Decrypt-then-Encrypt: operation of decrypting a ciphertext and then encrypting the decrypted ciphertext with another key). Non-patent Literature 2 provides a technique for obfuscating a Decrypt-then-Encrypt function, and cannot be utilized for obfuscating an StE function.
T. El Gamal, “A public key cryptosystem and signature scheme based on discrete logarithms,” IEEE Trans. Inform. Theory, Vol. 31, pp. 469-472, 1985 describes well-known encryption schemes. D. Boneh, B. Lynn, and H. Shacham, “Short Signatures from the Weil Pairing,” Proceedings of ASIACRYPT 2001, pp. 514-532, 2001, C. Schnorr, “Efficient Signature Generation by Smart Cards,” J. Cryptology 4(3), pp. 161-174, 1991, A. Lysyanskaya, “Unique Signatures and Verifiable Random Functions from the DH-DDH Separation,” Proceedings of CRYPTO '02, 2002, B. Waters, “Efficient Identity-Based Encryption Without Random Oracles,” Proceedings of Eurocrypt 2005 each describe a well-known signature scheme.